import {
  initializeVertexesColor,
} from '../utils/tools';
import {
  Queue,
} from '../Queue';
import {
  ObjectStack,
} from '../Stack';
import { COLORS_TXT, } from '../utils/constant';

export class Graph {
  protected isDirected: boolean;
  protected vertexes: any[];
  protected adjList: Map<any, any[]>;

  public constructor(isDirected = false) {
    this.isDirected = isDirected;
    this.vertexes = [];
    this.adjList = new Map();
  }

  public addVertex(v: any) {
    if (!this.vertexes.includes(v)) {
      this.vertexes.push(v);
      this.adjList.set(v, []);
    }
  }

  public addEdge(v: any, w: any) {
    if (!this.adjList.get(v)) {
      this.addVertex(v);
    }
    if (!this.adjList.get(w)) {
      this.addVertex(w);
    }
    this.adjList.get(v)?.push(w);
    if (!this.isDirected) {
      this.adjList.get(w)?.push(v);
    }
  }

  public toString() {
    let str = '';

    this.adjList.forEach((value, key) => {
      str += `${key} -->`;
      value.forEach(item => {
        str += ` ${item}`;
      });
      str += '\n';
    });

    return str;
  }

  public traverseDepth(vertexStart?: any) {
    return this.traverseDepthProtected(vertexStart);
  }

  public traverseWidth(vertexStart?: any, endCallback?: (...rest: any[]) => any) {
    return this.traverseWidthProtected(vertexStart, endCallback);
  }

  public getDepthDetil(vertexStart?: any): Map<any, {
    vBefore: any;
    timesFind: number | undefined;
    timesExplore: number | undefined;
  }> {
    const details: Map<any, {
      vBefore: any;
      timesFind: number | undefined;
      timesExplore: number | undefined;
    }> = new Map();
    let flag = 0;

    this.traverseDepthProtected(vertexStart, {
      findVCallback: (vFind, vBefore) => {
        const timeG = details.get(vFind);
        details.set(vFind, {
          vBefore,
          timesFind: ++flag,
          timesExplore: timeG?.timesExplore,
        });
      },
      exploreVCallback: (vExplore) => {
        const timeG = details.get(vExplore);
        details.set(vExplore, {
          vBefore: timeG?.vBefore,
          timesFind: timeG?.timesFind,
          timesExplore: ++flag,
        });
      }
    });

    return details;
  }

  public searchShortestPath(vertexFrom: any, vertexTo: any) {
    if (!this.vertexes.includes(vertexFrom)) {
      return `Vertex ${vertexFrom} is not existing !`;
    }

    if (!this.vertexes.includes(vertexTo)) {
      return `Vertex ${vertexTo} is not existing !`;
    }
    
    const { seniors, distance } = this.getEachShortestPath(vertexFrom);
    let vBeforeEnd = seniors.get(vertexTo);
    
    if (vBeforeEnd !== undefined) {
      const path = new ObjectStack();
      path.push(vertexTo);
      path.push(vBeforeEnd);
      while(vBeforeEnd !== vertexFrom) {
        vBeforeEnd = seniors.get(vBeforeEnd);
        path.push(vBeforeEnd);
      }

      let str = `${path.pop()}`;

      while (!path.isEmpty()) {
        str += ` => ${path.pop()}`;
      }

      return {
        distance: distance.get(vertexTo),
        path: str,
      };
    }
    return undefined;
  }

  public sortTopo() {
    let rings: [any, any][] = [];

    if (!this.isDirected) {
      return 'The graph isn\'t the directed graph !';
    }

    this.traverseDepthProtected(this.vertexes[0], {
      callback: (res) => {
        rings = res.ring;
      }
    });

    if (rings.length > 0) {
      return `The graph has rings '${rings.map(item => item.join(' - ')).join(',')}' !`;
    }
    
    const resultDFS = this.getDepthDetil();

    return [...resultDFS].sort((b, a) => {
      if (a[1].timesExplore && b[1].timesExplore) {
        return a[1].timesExplore - b[1].timesExplore;
      }
      return 0;
    }).map(item => item[0]);
  }

  protected traverseWidthProtected(vertexStart?: any, endCallback?: (...rest: any[]) => any, findVCallback?: (vFind: any, vExplore: any) => any) {
    const itemStart = this.vertexes.includes(vertexStart) ? vertexStart : this.vertexes[0];
    const queue = new Queue(itemStart);
    const colors = initializeVertexesColor(this.vertexes);
    const list: any[] = [];

    colors.set(itemStart, COLORS_TXT.GRAY);

    while (!queue.isEmpty()) {
      const item = queue.dequeue();
      const children = this.adjList.get(item);

      children?.forEach(child => {
        if (colors.get(child) === COLORS_TXT.WHITE) {
          queue.enqueue(child);
          colors.set(child, COLORS_TXT.GRAY);
          findVCallback?.(child, item);
        }
      });

      list.push(item);
      colors.set(item, COLORS_TXT.BLACK);

      if (queue.isEmpty()) {
        let entries = colors.entries();
        let next = entries.next();
        let value = next.value;

        while(!next.done) {
          if (value[1] === COLORS_TXT.WHITE) {
            queue.enqueue(value[0]);
            colors.set(value[0], COLORS_TXT.GRAY);
            findVCallback?.(value[0], undefined);
            break;
          } else {
            next = entries.next();
            value = next.value;
          }
        }
      }
    }

    endCallback?.(list);
    return list;
  }
  
  protected getEachShortestPath(vertexStart: any): {
    distance: Map<any, number | undefined>;
    seniors: Map<any, any>;
  } {
    const distance: Map<any, number | undefined> = new Map();
    const seniors: Map<any, any> = new Map();

    for (let value of  this.vertexes) {
      distance.set(value, 0);
    }

    this.traverseWidthProtected(vertexStart, undefined, (vFind, vExplore) => {
      const distanceS = distance.get(vExplore);
      const isNoDis = (distanceS && false) ?? true;
      distance.set(vFind, isNoDis ? undefined : (distanceS ?? 0) + 1);
      seniors.set(vFind, vExplore);
    });

    return {
      distance,
      seniors,
    };
  }

  protected traverseDepthProtected(
    vertexStart?: any,
    callBacks?: {
      findVCallback?: (vFind: any, vBefore: any) => any,
      exploreVCallback?: (vExplore) => any,
      callback?: (res: {
        list: any[],
        ring: [any, any][],
      }) => any
    }
  ) {
    const { findVCallback, exploreVCallback, callback } = (callBacks || {});
    const itemStart = this.vertexes.includes(vertexStart) ? vertexStart : this.vertexes[0];
    const stack = new ObjectStack(itemStart);
    const colors = initializeVertexesColor(this.vertexes);
    const list: any[] = [itemStart];
    const ring: [any, any][] = [];
    
    colors.set(itemStart, COLORS_TXT.GRAY);
    
    findVCallback?.(itemStart, itemStart);

    while (!stack.isEmpty()) {
      const peak = stack.peak();
      const neighbors = this.adjList.get(peak);
      const neighborNoFindHas = neighbors?.some(neighbor => {
        const isNotFind = colors.get(neighbor) === COLORS_TXT.WHITE;
        if (isNotFind) {
          stack.push(neighbor);
          colors.set(neighbor, COLORS_TXT.GRAY);
          list.push(neighbor);
          findVCallback?.(neighbor, peak);
        } else if (colors.get(neighbor) === COLORS_TXT.GRAY) {
          ring.push([neighbor, peak]);
        }
        return isNotFind;
      });

      if (!neighborNoFindHas) {
        const itemPop = stack.pop();
        colors.set(itemPop, COLORS_TXT.BLACK);
        exploreVCallback?.(itemPop);
      }

      if (stack.isEmpty()) {
        let entries = colors.entries();
        let next = entries.next();
        let value = next.value;
        
        while(!next.done) {
          if (value[1] === COLORS_TXT.WHITE) {
            stack.push(value[0]);
            colors.set(value[0], COLORS_TXT.GRAY);
            list.push(value[0]);
            findVCallback?.(value[0], undefined);
            break;
          } else {
            next = entries.next();
            value = next.value;
          }
        }
      }
    }
    callback?.({
      list,
      ring,
    });
    return list;
  }
}
